Grokking Meta Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Meta Easy Problems
Toeplitz Matrix (easy)
Solution: Toeplitz Matrix
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Island Perimeter (easy)
Solution: Island Perimeter
Moving Average from Data Stream (easy)
Solution: Moving Average from Data Stream
Move Zeroes (easy)
Solution: Move Zeroes
Missing Ranges (easy)
Solution: Missing Ranges
Palindrome Permutation (easy)
Solution: Palindrome Permutation
Rank Transform of an Array (easy)
Solution: Rank Transform of an Array
Meta Medium Problems
Diagonal Traverse (medium)
Solution: Diagonal Traverse
Shortest Path in Binary Matrix (medium)
Solution: Shortest Path in Binary Matrix
Maximum Swap (medium)
Solution: Maximum Swap
Custom Sort String (medium)
Solution: Custom Sort String
Binary Tree Vertical Order Traversal (medium)
Solution: Binary Tree Vertical Order Traversal
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Basic Calculator II (medium)
Solution: Basic Calculator II
Nested List Weight Sum (medium)
Solution: Nested List Weight Sum
Dot Product of Two Sparse Vectors (medium)
Solution: Dot Product of Two Sparse Vectors
Max Consecutive Ones III (medium)
Solution: Max Consecutive Ones III
Subarray Sum Equals K (medium)
Solution: Subarray Sum Equals K
Next Permutation (medium)
Solution: Next Permutation
Simplify Path (medium)
Solution: Simplify Path
Lowest Common Ancestor of a Binary Search Tree (medium)
Solution: Lowest Common Ancestor of a Binary Search Tree
'K' Closest Points to the Origin (medium)
Solution: 'K' Closest Points to the Origin
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Merge Intervals (medium)
Solution: Merge Intervals
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Number of Islands (medium)
Solution: Number of Islands
Clone Graph (medium)
Solution: Clone Graph
Missing Element in Sorted Array (medium)
Solution: Missing Element in Sorted Array
Number of Substrings Containing All Three Characters (medium)
Solution: Number of Substrings Containing All Three Characters
Capacity To Ship Packages Within D Days (medium)
Solution: Capacity To Ship Packages Within D Days
Count and Say (medium)
Solution: Count and Say
Contiguous Array (medium)
Solution: Contiguous Array
Sliding Window Median (hard)
Solution: Sliding Window Median
Alien Dictionary (hard)
Solution: Alien Dictionary
Minimum Window Substring (hard)
Solution: Minimum Window Substring
Best Meeting Point (hard)
Solution: Best Meeting Point
Maximum Sum of 3 Non-Overlapping Subarrays (hard)
Solution: Maximum Sum of 3 Non-Overlapping Subarrays
Making A Large Island (hard)
Solution: Making A Large Island
Basic Calculator (Hard)
Solution: Basic Calculator
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Longest Increasing Path in a Matrix (hard)
Solution: Longest Increasing Path in a Matrix
Valid Palindrome III (hard)
Solution: Valid Palindrome III
Solution: Subarray Sum Equals K

Problem Statement

Given an array nums containing n integers and integer k, return the total number of subarrays having sum equal to k.

A subarray is defined as a contiguous non-empty sequence of the array elements.

Examples

Example 1:

  • Input: nums = [1, 2, 3], k = 3
  • Expected Output: 2
  • Justification: There are two subarrays that sum to 3: [1, 2] and [3].

Example 2:

  • Input: nums = [10, 2, -2, -20, 10], k = -10
  • Expected Output: 3
  • Justification: Three subarrays sum up to -10: [10, 2, -2, -20], [2, -2, -20, 10], and [-20, 10].

Example 3:

  • Input: nums = [5, 1, 2, -3, 4, -2], k = 3
  • Expected Output: 2
  • Justification: There are two subarrays that sum to 3: [2, -3, 4], and [1, 2].

Solution

To solve this problem, we'll employ a technique that involves using a hashmap to efficiently track the cumulative sum of elements as we iterate through the array. The core idea is that if the cumulative sum up to two indices, say i and j, differs by the target value k, then the sum of the elements lying between i and j is k.

The algorithm will iterate through the array, calculating the cumulative sum at each step. We then check if (cumulative sum - k) is present in the hashmap. If it is, it means there exists a previous cumulative sum such that the difference between the current sum and that sum equals k, indicating a valid subarray. We add the count of these occurrences to our total. Additionally, we keep updating the hashmap with the count of each cumulative sum encountered. This approach is effective as it allows us to find the required subarrays in a single pass through the array, making it efficient in terms of time complexity.

Step-by-step Algorithm

  • Initialize a variable count to 0 and a hashmap cumulativeSumFrequency with a key-value pair (0:1) to handle edge cases.
  • Iterate through the array nums while keeping track of the cumulativeSum.
  • For each element num in nums:
    • Add num to cumulativeSum.
    • Check if (cumulativeSum - k) is in cumulativeSumFrequency. If it is, add its frequency to count.
    • Update cumulativeSumFrequency by incrementing the count of cumulativeSum.
  • Return the value of count.

Algorithm Walkthrough

Let's walk through the algorithm with Example 2: nums = [10, 2, -2, -20, 10], k = -10.

  • Start with cumulativeSum = 0, count = 0, cumulativeSumFrequency = {0: 1}.
  • For num = 10: cumulativeSum = 10. (cumulativeSum - k) = 20 is not in cumulativeSumFrequency. Update cumulativeSumFrequency to {0: 1, 10: 1}.
  • For num = 2: cumulativeSum = 12. (cumulativeSum - k) = 22 is not in cumulativeSumFrequency. Update cumulativeSumFrequency to {0: 1, 10: 1, 12: 1}.
  • For num = -2: cumulativeSum = 10. (cumulativeSum - k) = 20 is not in cumulativeSumFrequency. Update cumulativeSumFrequency to {0: 1, 10: 2, 12: 1}.
  • For num = -20: cumulativeSum = -10. (cumulativeSum - k) = 0 is in cumulativeSumFrequency. Add 1 to count. Update cumulativeSumFrequency to {0: 1, 10: 2, 12: 1, -10: 1}.
  • For num = 10: cumulativeSum = 0. (cumulativeSum - k) = 10 is in cumulativeSumFrequency with frequency 2.

Add 2 to count. Update cumulativeSumFrequency to {0: 2, 10: 2, 12: 1, -10: 1}.

  • Final count is 3.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the input array. This is due to a single loop through the array and constant-time hashmap operations.
  • Space Complexity: O(n), where n is the length of the input array. The primary space usage is the hashmap storing the cumulative sum frequencies, which in the worst case can grow to the size of the array.
Subarray Sum Equals K (medium)
Next Permutation (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis